package dp.公共子序列;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最长回文子序列516.java
 * @createTime 2024年04月26日 16:27:00
 */
public class 最长回文子序列516 {
	/*
   定义函数dp(i,j)表示位置i到j的子序列的最长的长度是dp[i][j]
   如果
   i=j dp[i][j]=dp[i+1][j-1]+2
   如果
   i≠j dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);

   baseCase:
   任意长度为1的位置都是回文串
	*/
	public int longestPalindromeSubseq(String s) {
		int len = s.length();
		int[][] dp = new int[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = 1;
		}
		for (int i = len - 1; i >= 0; i--) {
			for (int j = i + 1; j < len; j++) {
				if (s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i + 1][j - 1] + 2;
				} else {
					dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[0][len-1];
	}
}
